package com.example.demo.java.container.map;

/**
 * TreeMap最早出现在JDK 1.2中，是 Java 集合框架中比较重要一个的实现。
 * TreeMap 底层基于红黑树实现，可保证在log(n)时间复杂度内完成 containsKey、get、put 和 remove 操作，
 * 效率很高。另一方面，由于 TreeMap 基于红黑树实现，这为 TreeMap 保持键的有序性打下了基础。总的来说，
 * TreeMap 的核心是红黑树，其很多方法也是对红黑树增删查基础操作的一个包装。所以只要弄懂了红黑树，TreeMap 就没什么秘密了。
 *
 * 默认根节点的颜色是黑色的，但为了保证规则5成立（红黑树特性参考HashMap），插入节点的颜色总是红色的，
 * 但这时候可能会造成规则4不成立，就需要进行调整，红黑树有两种调整操作：
 * 变色（改变节点的颜色）旋转（左旋转和右旋转）
 *
 * 推荐文章：http://www.tianxiaobo.com/2018/01/11/TreeMap%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/
 */
public class UDTreeMap {

    /** 核心源码分析 */

        /** 1.查找 */
            //    public V get(Object key) {
            //        TreeMap.Entry<K, V> p = this.getEntry(key);
            //        return p == null ? null : p.value;
            //    }

            //    final TreeMap.Entry<K, V> getEntry(Object key) {
                      /** 1.如果key有自己的表叫规则，旧调用getEntryUsingComparator，比较获取具体值 */
            //        if (this.comparator != null) {
            //            return this.getEntryUsingComparator(key);
            //        } else if (key == null) {
            //            throw new NullPointerException();
            //        } else {
            //            Comparable<? super K> k = (Comparable)key;
            //            TreeMap.Entry p = this.root;
            //
            //            while(p != null) {
                              /** 2.比较key与红黑树节点的key值 */
            //                int cmp = k.compareTo(p.key);
                              /** 3.key小于红黑树节点的key，则从左侧继续查找 */
            //                if (cmp < 0) {
            //                    p = p.left;
            //                } else {
                                  /** 4.key相等时，直接返回查找结果 */
            //                    if (cmp <= 0) {
            //                        return p;
            //                    }
                                  /** 5.key大于红黑树节点的key，则从右侧继续查找 */
            //                    p = p.right;
            //                }
            //            }
            //
            //            return null;
            //        }
            //    }

        /** 2.遍历：根据key值进行遍历 */

        /** 3.插入
                相对于前两个操作，插入操作明显要复杂一些。当往 TreeMap 中放入新的键值对后，
                可能会破坏红黑树的性质。这里为了描述方便，把 Entry 称为节点。并把新插入的节点称为N，
                N 的父节点为P。P 的父节点为G，且 P 是 G 的左孩子。P 的兄弟节点为U。在往红黑树中插入新的节点 N 后（新节点为红色），
                会产生下面5种情况：

                     1、N 是根节点
                     2、N 的父节点是黑色
                     3、N 的父节点是红色，叔叔节点也是红色
                     4、N 的父节点是红色，叔叔节点是黑色，且 N 是 P 的右孩子
                     5、N 的父节点是红色，叔叔节点是黑色，且 N 是 P 的左孩子

                    上面5中情况中，情况2不会破坏红黑树性质，所以无需处理。情况1 会破坏红黑树性质2（根是黑色），
                    情况3、4、和5会破坏红黑树性质4（每个红色节点必须有两个黑色的子节点）。这个时候就需要进行调整，以使红黑树重新恢复平衡。
         */
            //    public V put(K key, V value) {
            //        TreeMap.Entry<K, V> t = this.root;
                      /** 1.如果根节点为 null，将新节点设为根节点 */
            //        if (t == null) {
            //            this.compare(key, key);
            //            this.root = new TreeMap.Entry(key, value, (TreeMap.Entry)null);
            //            this.size = 1;
            //            ++this.modCount;
            //            return null;
            //        } else {
            //            Comparator<? super K> cpr = this.comparator;
            //            int cmp;
            //            TreeMap.Entry parent;
                         /** 2.自定义key的比较规则时 */
            //            if (cpr != null) {
            //                do {
            //                    parent = t;
                                  /** 2.1 根据比较规则，判断往左还是往右，找到红黑树存储节点的位置 */
            //                    cmp = cpr.compare(key, t.key);
            //                    if (cmp < 0) {
            //                        t = t.left;
            //                    } else {
            //                        if (cmp <= 0) {
            //                            return t.setValue(value);
            //                        }
            //
            //                        t = t.right;
            //                    }
            //                } while(t != null);
            //            } else {
                              /** 3.使用key默认的比较规则 */
            //                if (key == null) {
            //                    throw new NullPointerException();
            //                }
            //
            //                Comparable k = (Comparable)key;
            //
            //                do {
            //                    parent = t;
                                  /** 3.1 根据比较规则，判断往左还是往右，找到红黑树存储节点的位置 */
            //                    cmp = k.compareTo(t.key);
            //                    if (cmp < 0) {
            //                        t = t.left;
            //                    } else {
            //                        if (cmp <= 0) {
            //                            return t.setValue(value);
            //                        }
            //
            //                        t = t.right;
            //                    }
            //                } while(t != null);
            //            }
                          /** 4.创建新节点，并根据比较结果，放入相应的左/右子树中 */
            //            TreeMap.Entry<K, V> e = new TreeMap.Entry(key, value, parent);
            //            if (cmp < 0) {
            //                parent.left = e;
            //            } else {
            //                parent.right = e;
            //            }
                          /** 5.插入新节点可能会破坏红黑树性质，这里修正一下（红黑树相关操作：左旋、右旋、变色、换位等等） */
            //            this.fixAfterInsertion(e);
            //            ++this.size;
            //            ++this.modCount;
            //            return null;
            //        }
            //    }

        /** 4.删除
                从源码中可以看出，remove方法只是一个简单的保证，核心实现在deleteEntry方法中。deleteEntry 主要做了这么几件事：
                     1、如果待删除节点 P 有两个孩子，则先找到 P 的后继 S，然后将 S 中的值拷贝到 P 中，并让 P 指向 S
                     2、如果最终被删除节点 P（P 现在指向最终被删除节点）的孩子不为空，则用其孩子节点替换掉
                     3、如果最终被删除的节点是黑色的话，调用 fixAfterDeletion 方法进行修复
                上面说了 replacement 不为空时，deleteEntry 的执行逻辑。上面说的略微啰嗦，如果简单说的话，
                7个字即可总结：找后继 -> 替换 -> 修复。这三步中，最复杂的是修复操作。修复操作要重新使红黑树恢复平衡
         */
            //    public V remove(Object key) {
            //        TreeMap.Entry<K, V> p = this.getEntry(key);
            //        if (p == null) {
            //            return null;
            //        } else {
            //            V oldValue = p.value;
            //            this.deleteEntry(p);
            //            return oldValue;
            //        }
            //    }

            //    private void deleteEntry(TreeMap.Entry<K, V> p) {
            //        ++this.modCount;
            //        --this.size;
            //        TreeMap.Entry replacement;
                      /**
                       * 1. 如果 p 有两个孩子节点，则找到后继节点，
                       * 并把后继节点的值复制到节点 P 中，并让 p 指向其后继节点
                       */
            //        if (p.left != null && p.right != null) {
            //            replacement = successor(p);
            //            p.key = replacement.key;
            //            p.value = replacement.value;
            //            p = replacement;
            //        }
            //
            //        replacement = p.left != null ? p.left : p.right;
            //        if (replacement != null) {
                          /**
                           * 2. 将 replacement parent 引用指向新的父节点，
                           * 同时让新的父节点指向 replacement。
                           */
            //            replacement.parent = p.parent;
            //            if (p.parent == null) {
            //                this.root = replacement;
            //            } else if (p == p.parent.left) {
            //                p.parent.left = replacement;
            //            } else {
            //                p.parent.right = replacement;
            //            }
            //
            //            p.left = p.right = p.parent = null;
                          /** 3. 如果删除的节点 p 是黑色节点，则需要进行调整 */
            //            if (p.color) {
            //                this.fixAfterDeletion(replacement);
            //            }
            //        } else if (p.parent == null) {
                          /** 4.删除的是根节点，且树中当前只有一个节点 */
            //            this.root = null;
            //        } else {
                          /**
                           * 5.删除的节点没有孩子节点
                           * p 是黑色，则需要进行调整
                           */
            //            if (p.color) {
            //                this.fixAfterDeletion(p);
            //            }
                          /** 6.将 P 从树中移除 */
            //            if (p.parent != null) {
            //                if (p == p.parent.left) {
            //                    p.parent.left = null;
            //                } else if (p == p.parent.right) {
            //                    p.parent.right = null;
            //                }
            //
            //                p.parent = null;
            //            }
            //        }
            //
            //    }

}
